import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 554. 砖墙
 * <a href="https://leetcode.cn/problems/brick-wall/description/">...</a>
 * User: DELL
 * Date: 2023-11-07
 * Time: 23:38
 */
public class Solution {
    /**
     * 解题思路: (哈希表)
     * 本题最主要的一点是观察出任意一条垂线，穿过的砖块的数量 + 从边缘经过的砖块的数量 = n
     * 因此只需要找出一条经过最多砖块边缘的垂线即可。
     * 因此我们初步的想法就可以使用一个一维数组来记录每一条垂线上的砖块边缘的数量即可，这
     * 样子的空间复杂度为 O(N) (N = 一层砖块的宽度)，但是题目中每一层砖块的宽度达到了
     * int类型的最大值，因此这显然不行，但是题目又规定砖块的总数是小于 2*10^4，因此
     * 砖块边缘的数量其实也不多的，因此就只需要记录砖块边缘即可。
     * 因此就转变思路，使用哈希表来统计即可。
     *
     * @param wall
     * @return
     */
    public int leastBricks(List<List<Integer>> wall) {
        int n = wall.size();
        // 计算一行的总和，以此来确定数组的长度
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < wall.size(); i++) {
            List<Integer> list = wall.get(i);
            int temp = 0;
            for (int j = 0; j < list.size() - 1; j++) {
                temp += list.get(j);
                hashMap.put(temp, hashMap.getOrDefault(temp, 0) + 1);
            }
        }
        int max = 0;
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            max = Math.max(max, entry.getValue());
        }
        return n - max;
    }
}
